import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
 * Implements the disjointSets data structure that contains a number of non-overlapping sets of vertices
 * @author BaoTam
 *
 */
public class DisjointSets {
	
	private Map<Vertex, Vertex> childToParentMap;
	private Map<Vertex, Integer> rootToRankMap;
	
	/**
	 * This constructor could do any number of things. Feel free to add instance
	 * variables if you need them. You may assume the methods sameSet, and merge
	 * will only be called with vertices that are in the set vertex set passed
	 * in here
	 * 
	 * @param vertices
	 *            All vertices that are valid parameters for this disjoint set
	 */
	public DisjointSets(Set<Vertex> vertices) {
		childToParentMap = new HashMap<Vertex, Vertex>();
		rootToRankMap	  = new HashMap<Vertex, Integer>();
		if(vertices == null) {
			return;
		}
		Iterator<Vertex> vertexSetIterator = vertices.iterator();
		while(vertexSetIterator.hasNext()) {
			Vertex v = vertexSetIterator.next();
			childToParentMap.put(v, null);
			rootToRankMap.put(v, 0);
		}
	}
	
	/**
	 * find the root of the vertex v and perform path compression along the way
	 * @param v
	 * @return
	 */
	public Vertex findRoot(Vertex v) {
		if(v == null || !childToParentMap.containsKey(v)) {
			return null;
		}
		
		Vertex parent = childToParentMap.get(v);
		if(parent == null) {
			return v;
		}
		
		childToParentMap.put(v, findRoot(parent));
		return childToParentMap.get(v);
	}

	/**
	 * Returns true if and only if u and v belong to the same set.
	 * 
	 * Hint: a "Vertex find(Vertex v)" helper might be useful.
	 * 
	 * @param u
	 * @param v
	 * @return
	 */
	public boolean sameSet(Vertex u, Vertex v) {
		if(u == null || v == null || !childToParentMap.containsKey(u) || !childToParentMap.containsKey(v)) {
			return false;
		}
		return findRoot(u).equals(findRoot(v));
	}

	/**
	 * Merges the set containing u with the set containing v. If u and v are in
	 * the same set do nothing
	 * 
	 * @param u
	 * @param v
	 */
	public void merge(Vertex u, Vertex v) {
		if(u == null || v == null || !childToParentMap.containsKey(u) || !childToParentMap.containsKey(v) || sameSet(u,v)) {
			return;
		}
		
		Vertex rootLargerRank;
		Vertex rootSmallerRank;
		
		if(rootToRankMap.get(findRoot(u)).compareTo(rootToRankMap.get(findRoot(v))) > 0) {
			rootLargerRank = findRoot(u);
			rootSmallerRank = findRoot(v);
		}
		else {
			rootLargerRank = findRoot(v);
			rootSmallerRank = findRoot(u);
		}
		childToParentMap.put(rootSmallerRank, rootLargerRank);
		rootToRankMap.put(rootLargerRank, rootToRankMap.get(rootSmallerRank) + rootToRankMap.get(rootLargerRank) + 1);
		rootToRankMap.remove(rootSmallerRank);
		
	}
	
	/**
	 * @return the string representation of the disjointSets
	 */
	public String toString() {
		String result = "{";
		Map<Vertex, List<Vertex>> setMap = new HashMap<Vertex, List<Vertex>>();
		
		Iterator<Vertex> parentMapIterator = childToParentMap.keySet().iterator();
		while(parentMapIterator.hasNext()) {
			Vertex v = parentMapIterator.next();
			Vertex root = findRoot(v);
			
			if(!setMap.containsKey(root)) {
				setMap.put(root, new LinkedList<Vertex>());
			}
			
			setMap.get(root).add(v);
			
		}
		
		Iterator<Vertex> setMapIterator = setMap.keySet().iterator();
		while(setMapIterator.hasNext()) {
			Vertex root = setMapIterator.next();
			result += root + ": " + setMap.get(root).toString() + " | ";
		}
		result += "}";
		return result;
	}
	
	/**
	 * main method for debugging purpose
	 * @param args
	 */
	public static void main(String[] args) {
		Integer[] intArr = {10,9,4,5,2,1,11,4,6};
		Set<Vertex> vertexSet = new HashSet<Vertex>();
		for(Integer i : intArr) {
			vertexSet.add(new Vertex(i));
		}
		
		DisjointSets disjSets = new DisjointSets(vertexSet);
		System.out.println(disjSets);
		while(true) {
			System.out.print("$$ ");
			Scanner scanner = new Scanner(System.in).useDelimiter("[^a-zA-Z0-9]+");
			String instruction = scanner.next();
			System.out.println(instruction);
			if(instruction.equals("end")) {
				break;
			}
			if(instruction.equals("merge")) {
				Vertex u = new Vertex(scanner.nextInt());
				Vertex v = new Vertex(scanner.nextInt());
				System.out.println("\tmerge begin: u: " + u + ", v: " + v);
				System.out.println("\tparentMap: " + disjSets.childToParentMap);
				disjSets.merge(u,v);
				System.out.println("\t" + disjSets);
			}
			else {
				continue;
			}
		}
	}
}
